1. The Field of the Invention
This invention relates to displaying realistic images on a graphical display. More specifically, the present invention relates to the rendering of realistic shadows cast by displayed objects relative to the objects and a perceived light source to thereby provide greater realism or image enhancement to an image shown on a graphical display.
2. The State of the Art
The ability to accurately and rapidly render images on a graphical display is much sought after. Accordingly, a definition or understanding which will be useful in describing the invention is that the image of concern is not just a picture showing three-dimensional objects which cannot be manipulated; rather in the image of the present invention, at least one object which can be viewed on a graphical display may be manipulated by computational means. In other words, the objects we are concerned with are three-dimensional "things" which can be displayed realistically as a two-dimensional image.
A less abstract example which clarifies the definition above is shown in FIG. 1. Here a two-dimensional image is illustrated because it is drawn on a two-dimensional piece of paper. Likewise, FIG. 1 does not differ significantly from what would be displayed on a computer graphical display. However, despite being a two-dimensional image, the image appears to have depth because the image is rendered with perspective. In FIG. 1, the rendered image shows terrain or landscaping 10, a light source 12 and a three-dimensional object 14 which is disposed perpendicular to the underlying terrain 10. Given the location of the object 14 and the location of the light source 12, the object should cast a shadow relative to the light source 12. The area 16 shaded by the object 14 is simply shown for the sake of identifying the area 16 which should be shaded. The shaded area 16, however, is not yet rendered with a shadow.
FIG. 1 illustrates the concept that a perspective view of an object 14 gives an observer a sense of depth so that the object appears to be more real than a two-dimensional image. In other words, the purpose of a perspective view is to make a two-dimensional image appear three-dimensional. The relevance of this last statement is that an object 14 can appear to be more realistic and accurate if rendered properly.
The importance of rendering a realistic or more life-like image comes from the advantages to be gained from visualizing objects or scenes that do not exist, do not yet exist, or which exist but do not provide enough information (visual clues as to what is being viewed) when seen in reality. Particular examples will be described later. What should be remembered, however, is that a vital component of any realistic or enhanced image rendering process, and which is often ignored, is the casting and rendering of shadows. A shadow not only provides an obvious clue as to the direction of a light source, more importantly for displayed computer images, it enhances visual reality to help the mind believe what it is seeing.
Thus, while the importance of shadows in rendering realistic images on a computer display has long been recognized, the ability to accurately render them has been difficult. This difficulty can be summarized as a problem with rendering accurate shadows, realistic shadows and rendering shadows in real-time.
The subject of rendering of shadows has been researched since the early days of computer graphics. For example, the published papers of Frank Crow in Shadow Algorithms for Computer Graphics, and Lance Williams in Casting Curved Shadows on Curved Surfaces, addressed handling of shadow edges, or penumbra, to improve realism and to prevent aliasing. In 1987, William Reeves, et al. published Rendering Antialiased Shadows with Depth Maps, where an algorithm for antialiasing shadows with depth maps was presented. Andrew Woo, et al. presented a survey of shadow rendering techniques which had been implemented up to 1990. Those techniques included hard and soft edged shadowing, scanline approaches, using shadow volumes, area subdivision, depth buffering, ray tracing, cone tracing, radiosity, etc. The survey even addressed various culling schemes, transparency effects, and shadows caused by bumpy surfaces.
While rendering realistic shadows is difficult, the problem is compounded when the objects and/or scene are modeled by complex databases which contain a mathematical description of three-dimensional objects. In the past, non-real-time techniques have often turned to ray tracing or radiosity techniques to achieve realism. However, these techniques are not directly applicable to systems requiring fast rendering, such as in real-time or interactive image generators.
In 1992, Mark Segal, et al. introduced an algorithm for using texture mapping hardware to render shadows. The algorithm is based on the work of William Reeves and what others have done with depth maps. Segal showed that a rendering pipeline could be used in multiple passes to render the image from both the light source's perspective and the observer's perspective. The texture mapping hardware is used to transform from one space to another. More specifically, a scene is first rendered from the perspective of the light source. The resulting depth values are then transferred from a frame buffer to a texture memory. When rendering the scene from the observer's perspective, each pixel is transformed via the texture hardware into the light source's space where it is compared with the depth stored in the texture memory. If the image's depth is further than the texture depth, the pixel is in a shadow.
While the technique above has generated some impressive demos, it is not a useful technique for complex applications. For example, when rendering a scene from the light source's perspective, the level of detail may be completely different than the level of detail seen by the observer. This can cause inconsistencies in the shadows produced. These inconsistencies could even appear and disappear in sequential images, thereby causing distracting effects, as the eye position or light source moves. In addition, the cost of the hardware is doubled or tripled in order to accomplish the multiple passes.
Another problem is that because the resultant depth map must be converted to a texture map, it is very limited in its resolution. This can result in very coarse shadow images. This can be amplified if the light source is omni-directional. An omni-directional light source can illuminate any point in an image database, so the first pass rendering must have a field-of-view which completely encloses the observers field-of-view. This can severely limit the applied resolution.
Another problem is that the use of textures for the depth map increases the number of texture maps that must be applied to the polygon. The result is an increase in the rendering time which may exceed the limits of the hardware.
A last notable problems is that the depth texture map must be applied to the entire terrain model. This process involves complex clipping for any terrain triangle that is not completely enclosed by the shadow's texture map.
In summary, while many of the published shadow rendering techniques provide robust, general purpose solutions, none of the general solutions can be implemented in real-time hardware. What is needed is a shadow rendering technique which can be used to generate realistic and accurate shadows for display in real-time or interactively to thereby avoid the common problems cited above.